// 给出 n 个数对。 在每一个数对中，第一个数字总是比第二个数字小。
// 现在，我们定义一种跟随关系，当且仅当 b < c 时，数对(c, d) 才可以跟在 (a, b) 后面。我们用这种形式来构造一个数对链。
// 给定一个数对集合，找出能够形成的最长数对链的长度。你不需要用到所有的数对，你可以以任何顺序选择其中的一些数对来构造。
/**
 * @param {number[][]} pairs
 * @return {number}
 */
var findLongestChain = function (pairs) {
  // 排序，以数对第二个元素递增排序
  pairs.sort((a, b) => {
    return a[1] - b[1];
  })
  // 栈顶指针指向当前res栈顶
  let res = [pairs[0]], top = 0;
  for (let i = 1; i < pairs.length; i++) {
    if (pairs[i][0] > res[top][1]) {
      res.push(pairs[i]);
      top++;
    }
  }
  return res.length;
};
console.log(findLongestChain([[1, 10], [2, 3], [3, 4], [4, 8], [4, 5]]));
console.log(findLongestChain([[1, 2], [2, 3], [3, 4]]));